'''
    py-sudoku-solver-sdj : A Python Sudoku Grid Solver written in Python
    
    Version: 0.5.2
        
    Copyright (C) 2012  Steve De Jongh stdj79(at)gmail(dot)com

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
'''

def seq_in_seq(subseq, seq):
    while subseq[0] in seq:
        index = seq.index(subseq[0])
        if subseq == seq[index:index + len(subseq)]:
            return index
        else:
            seq = seq[index + 1:]
    else:
        return -1
    
def isSubList(sublist,list):
    result = True
    for item in sublist:
        if item not in list:
            result = False
    return result

class Cell(object):
    '''Sudoku Grid cell object'''
    def __init__(self,x,y,value=0):
        ''' Class constructor '''
        self.value = value
        self.possibilities = []
        self.x = x
        self.y = y
    def addPossibility(self,value):
        ''' Add one value to cell.possibilities '''
        if value not in self.possibilities:
            self.possibilities.append(value)
    def delPossibility(self,value):
        ''' Remove one value from cell.possibilities '''
        if value in self.possibilities:
            self.possibilities.remove(value)
    def getPossibilities(self):
        ''' Returns cell.possibilities '''
        return self.possibilities
    def getCount(self):
        ''' Returns count of cell possibilities '''
        return len(self.possibilities)
    def getSubgridId(self):
        ''' Returns the ID of the 3x3 subgrid the cell belogns to '''
        for i in range(1,10):
            (minX,maxX,minY,maxY) = SudokuArea.subGridsCoord[i]
            if ( minX <= self.x <= maxX ) and ( minY <= self.y <= maxY ):
                return i
        
              
class SudokuArea(object):
    '''Generic Sudoku Area'''
    subGridsCoord = {
                     1:(1,3,1,3),2:(4,6,1,3),3:(7,9,1,3),
                     4:(1,3,4,6),5:(4,6,4,6),6:(7,9,4,6),
                     7:(1,3,7,9),8:(4,6,7,9),9:(7,9,7,9),                     
                     }
    def __init__(self,xstart=0,xend=0,ystart=0,yend=0):
        ''' Class constructor '''
        self.xStart = xstart
        self.xEnd = xend
        self.yStart = ystart
        self.yEnd = yend
        self.allCells = {}
        self.missingValues = [1,2,3,4,5,6,7,8,9]
    def addCell(self,x,y,cellObj):
        ''' Add a new cell object to SudokuArea.allCells and updates SudokuArea.missingValues if the has a value defined '''
        self.allCells[(x,y)] = cellObj
        if cellObj.value != 0 and cellObj.value in self.missingValues:
            self.missingValues.remove(cellObj.value)
    def updateMissingValues(self):
        ''' Updates SudokuArea.missingValues content '''
        for cell in self.getCellsList():
            if cell.value in self.missingValues:
                self.missingValues.remove(cell.value)
                
    def getCellValue(self,x,y,string=False):
        ''' Returns cell value for the give x,y coordinate '''
        if self.allCells[(x,y)].value == 0:
            if string == False:
                value = 0
            else:
                value = " "
        else:
            if string == False:
                value = self.allCells[(x,y)].value
            else:
                value = self.allCells[(x,y)].value
        return value
    
    def getCellsList(self):
        ''' Returns a list of all cells object contained in the area '''
        return [self.allCells[cellid] for cellid in self.allCells]
    
    def getEmptyCellsList(self):
        ''' Returns the lists of allcells without final value in the area '''
        return [cell for cell in self.getCellsList() if cell.value == 0]
        
class SudokuRow(SudokuArea):
    '''Simple Sudoku grid row'''
    def __init__(self,y):
        SudokuArea.__init__(self,1,9,y,y)
        
class SudokuColumn(SudokuArea):
    '''Simple Sudoku grid column'''
    def __init__(self,x):
        SudokuArea.__init__(self,x,x,1,9)
        
class SudokuSubGrid(SudokuArea):
    '''3x3 Sudoku subgrid'''
    def __init__(self,aid):
        (minX,maxX,minY,maxY) = SudokuArea.subGridsCoord[aid]
        SudokuArea.__init__(self,minX,maxX,minY,maxY)
        
class SudokuGrid(SudokuArea):
    '''Complete Sudoku Grid'''
    def __init__(self):
        SudokuArea.__init__(self,1,1,9,9)
        self.gridColumns = {}
        self.gridRows = {}
        self.gridSubgrids = {}
        self.emptyCells = []
        for i in range(1,10):
            self.gridColumns[i] = SudokuColumn(i)
            self.gridRows[i] = SudokuRow(i)
            self.gridSubgrids[i] = SudokuSubGrid(i)
            
    def fillGrid(self,content):
        ''' Fill SudokuGrid.allCells using content dictionnary '''
        for item in content.keys():
            (x,y) = item
            newCell = Cell(x,y,content[item])
            if newCell.value == 0:
                self.emptyCells.append(newCell)
            self.addCell(x, y, newCell)
            self.gridRows[y].addCell(x,y,newCell)
            self.gridColumns[x].addCell(x,y,newCell)
            for i in range(1,10):
                (minX,maxX,minY,maxY) = SudokuArea.subGridsCoord[i]
                if ( minX <= x <= maxX ) and ( minY <= y <= maxY ):
                    self.gridSubgrids[i].addCell(x,y,newCell)
            
    def loadGridFromFile(self,gridfile):
        ''' Parses a grid file, and converts it into a dictionnary '''
        f = open(gridfile,'r')
        lines = [line.strip() for line in f]
        f.close()
        y = 1
        grid = {}
        for line in lines:
            x = 1
            for char in line:
                if char == "?":
                    value = 0
                else:
                    value = int(char)
                grid[(x,y)] = value
                x += 1
            y += 1
        self.fillGrid(grid)
    
    def display(self):
        ''' Displays the grid in its actual state '''
        print "+-------+-------+-------+"
        for j in range(0,3):
            for i in range(1,4):
                z = 3*j+i
                print "| {} {} {} | {} {} {} | {} {} {} |".format(self.getCellValue(1,z,True),self.getCellValue(2,z,True),self.getCellValue(3,z,True),
                                                                  self.getCellValue(4,z,True),self.getCellValue(5,z,True),self.getCellValue(6,z,True),
                                                                  self.getCellValue(7,z,True),self.getCellValue(8,z,True),self.getCellValue(9,z,True))
            print "+-------+-------+-------+"
            
    def getAreas(self,type):
        ''' Returns a list of all areas objects from the give type in the whole grid '''
        if type == "rows":
            return [self.gridRows[rowid] for rowid in self.gridRows]
        if type == "columns":
            return [self.gridColumns[colid] for colid in self.gridColumns]
        if type == "subgrids":
            return [self.gridSubgrids[gridid] for gridid in self.gridSubgrids]
        else:
            return None
    
    def setCellPossibilities(self,cellKey):
        ''' sets SudocuCell.posibilities analysing all other cells from the areas where the cell is '''
        cell = self.allCells[cellKey]
        (x,y) = cellKey
        if cell.value == 0:
            if len(cell.possibilities) > 0:
                cellPossibilities = []
                cellPossibilities.extend(cell.possibilities)
            else:
                cellPossibilities = [1,2,3,4,5,6,7,8,9]
        col = self.gridColumns[x]
        row = self.gridRows[y]
        grid = self.gridSubgrids[cell.getSubgridId()]
        for otherCell in col.getCellsList():
            if otherCell.value in cellPossibilities:
                cellPossibilities.remove(otherCell.value)
        for otherCell in row.getCellsList():
            if otherCell.value in cellPossibilities:
                cellPossibilities.remove(otherCell.value)
        for otherCell in grid.getCellsList():
            if otherCell.value in cellPossibilities:
                cellPossibilities.remove(otherCell.value)
        cell.possibilities = cellPossibilities
        
    def setCellValue(self,cell,value):
        cell.value = value
        cell.possibilities = []
        self.emptyCells.remove(cell)
        self.updatePossibilities("cell", (cell.x,cell.y))
        self.updateCellAreasMissingValues(cell)
    
    def methodNakedSingle(self):
        '''
        Method 0 : Unique possibility in cell method
        returns True if something has been found, else will return False
        '''
        foundSomething = False
        for cell in self.emptyCells:
            if len(cell.possibilities) == 1:
                print "...Found value {} in cell {}".format(str(cell.possibilities[0]),str((cell.x,cell.y)))
                self.setCellValue(cell, cell.possibilities[0])
                foundSomething = True
        return foundSomething
    
    def methodUniqueCandidate(self):
        '''
        Method 1 : Unique candidate in an area
        returns True if something has been found, else will return False
        '''
        foundSomething = False
        for cell in self.emptyCells:
            cellRow = self.gridRows[cell.y]
            cellCol = self.gridColumns[cell.x]
            cellSubgrid = self.gridSubgrids[cell.getSubgridId()]
            for possibility in cell.possibilities:
                (count,cells) = self.getPossibilityLocationInRow(possibility, cellRow)
                if count == 1 and foundSomething == False:
                    print "...(ROW) Found value {} in cell {}".format(str(possibility),str((cell.x,cell.y)))
                    self.setCellValue(cell, possibility)
                    foundSomething = True
                (count,cells) = self.getPossibilityLocationInColumn(possibility, cellCol)
                if count == 1 and foundSomething == False:
                    print "...(COL) Found value {} in cell {}".format(str(possibility),str((cell.x,cell.y)))
                    self.setCellValue(cell, possibility)
                    foundSomething = True
                (count,cells) = self.getPossibilityLocationInSubgrid(possibility, cellCol)
                if count == 1 and foundSomething == False:
                    print "...(SUB) Found value {} in cell {}".format(str(possibility),str((cell.x,cell.y)))
                    self.setCellValue(cell, possibility)
                    foundSomething = True
        return foundSomething
        
    def methodBlockInteraction(self):
        '''
        Method 2 : If a value can only be found on a row/col in a subgrid, then it can be removed from that row/col in other subgrids
        returns True if something has been found, else will return False
        '''
        foundSomething = False
        for subgrid in self.gridSubgrids:
            for value in self.gridSubgrids[subgrid].missingValues:
                (count,cells) = self.getPossibilityLocationInSubgrid(value,self.gridSubgrids[subgrid])
                rows, cols = [], []
                rows = [cell.y for cell in cells if cell.y not in rows]
                cols = [cell.x for cell in cells if cell.x not in cols]
                if len(rows) == 1 and foundSomething == False:
                    tmplist = []
                    tmplist.extend(self.gridRows[rows[0]].getEmptyCellsList())
                    for rowcell in tmplist:
                        if rowcell not in self.gridSubgrids[subgrid].getEmptyCellsList():
                            if value in rowcell.possibilities:
                                rowcell.delPossibility(value)
                                print "...(SUB/ROW) Removed value {} from cell {}".format(str(value),str((rowcell.x,rowcell.y)))
                                if len(rowcell.possibilities) == 1:
                                    print "...(SUB/ROW) Found value {} in cell {}".format(str(value),str((rowcell.x,rowcell.y)))
                                    self.setCellValue(rowcell, rowcell.possibilities[0])
                                    foundSomething = True
                if len(cols) == 1 and foundSomething == False:
                    tmplist = []
                    tmplist.extend(self.gridColumns[cols[0]].getCellsList())
                    for colcell in tmplist:
                        if colcell not in self.gridSubgrids[subgrid].getCellsList():
                            if value in colcell.possibilities:
                                colcell.delPossibility(value)
                                print "...(SUB/COL) Removed value {} from cell {}".format(str(value),str((colcell.x,colcell.y)))
                                if len(colcell.possibilities) == 1:
                                    print "...(SUB/COL) Found value {} in cell {}".format(str(value),str((colcell.x,colcell.y)))
                                    self.setCellValue(colcell, colcell.possibilities[0])
                                    foundSomething = True
            return foundSomething
    
    def methodNakedPair(self):
        '''
        Method 3 : Naked pair method
        returns True if some possibilities have been removed, else will return False
        '''
        foundSomething = False
        areaTypes = ["rows","columns","subgrids"]
        for areaType in areaTypes:
            print "[M3] Trying to find pairs in {}...".format(areaType)
            for area in self.getAreas(areaType):
                pairs = {}
                pairs = self.getPairsInArea(area)
                for pair in pairs:
                    if len(pairs[pair]) == 2:
                        cells = pairs[pair]
                        print "...Found pair {} in cells {} and {}".format(str(pair),str((cells[0].x,cells[0].y)),str((cells[1].x,cells[1].y)))
                        for areaCell in area.getEmptyCellsList():
                            if areaCell not in cells:
                                for value in pair:
                                    if value in areaCell.possibilities:
                                        areaCell.delPossibility(value)
                                        print "......Removed value {} from cell {} possibilities".format(str(value),str((areaCell.x,areaCell.y)))
                                        foundSomething = True       
        return foundSomething
    
    def methodSet(self,n):
        '''
        Generic method to find set of N values in N cells inside an area
        '''
        foundSomething = False
        areasDicts = [self.gridRows,self.gridColumns,self.gridSubgrids]
        for dict in areasDicts:
            areas = [dict[key] for key in dict]
        for area in areas:
            for cell in area.getEmptyCellsList():
                if cell.getCount() == n:
                    tripletcells = [othercell for othercell in area.getEmptyCellsList() if othercell.getCount() <= n and isSubList(othercell.possibilities,cell.possibilities)]
                    if len(tripletcells) == n:
                        print "... Found set of {} values".format(str(n))
                        for celltoclean in area.getEmptyCellsList():
                            if celltoclean not in tripletcells:
                                before = [] + celltoclean.possibilities
                                celltoclean.possibilities = list(set(celltoclean.possibilities) - set(cell.possibilities))
                                print ".... Removed value(s) {} from cell {}".format(str(list(set(before) - set(celltoclean.possibilities))),str((celltoclean.x,celltoclean.y)))
                                if len(list(set(before) - set(celltoclean.possibilities))) > 0:
                                    foundSomething = True               
        return foundSomething
    
    def methodTriplet(self):
        '''
        Method 4 : Triplet method
        If 3 value found in one cell can only be found in 3 cells (only those values in the 3 cells) in the area, then it can be remove from other cells in the area
        '''
        print "[M4] Trying to find triplets..."                      
        return self.methodSet(3)
    
    def methodQuartet(self):
        '''
        Method 5 : Quartet method
        If 4 value found in one cell can only be found in 4 cells (only those values in the 4 cells) in the area, then it can be remove from other cells in the area
        '''
        print "[M5] Trying to find quartets..."                      
        return self.methodSet(4)
    
    def methodPointingPair(self):
        '''
        Method 6 : If a pair of empty cells within a box in the same row or column share a given candidate, then that candidate can be removed from the candidate
        list of all other cells in the box if it is not a candidate of any other cells in the row or column. 
        '''
        foundSomething = False
        print "[M6] Trying to find pointing pairs..."
        for subgrid in self.getAreas("subgrids"):
            if subgrid.missingValues > 0:
                for value in subgrid.missingValues:
                    (count,cells) = self.getPossibilityLocationInSubgrid(value, subgrid)
                    rows, cols = [], []
                    rows = list(set([cell.y for cell in cells if cell.y not in rows]))
                    cols = list(set([cell.x for cell in cells if cell.x not in cols]))
                    if len(rows) == 1:
                        for othercell in self.gridRows[cell.y].getEmptyCellsList():
                            if othercell not in subgrid.getEmptyCellsList():
                                if value in othercell.possibilities:                
                                    othercell.delPossibility(value)
                                    print "...Removed value {} from cell {} possibilities".format(str(value),str((othercell.x,othercell.y)))
                                    foundSomething = True
                    if len(cols) == 1:
                        for othercell in self.gridColumns[cell.x].getEmptyCellsList():
                            if othercell not in subgrid.getEmptyCellsList() :
                                if value in othercell.possibilities:
                                    othercell.delPossibility(value)
                                    print "...Removed value {} from cell {} possibilities".format(str(value),str((othercell.x,othercell.y)))
                                    foundSomething = True
        return foundSomething
           
    def solve(self,method=0):
        '''
            Grid Solver Methods:
            0 = if a cell has only one possibility then it is its real value
            1 = if a number only appears once in an area, then it is the value of the cell where it was found
            2 = if in a subgrid a value can only be found in one row (or column) then it can be removed from other subgrids cells on the same row (or column)
            3 = Naked pair method
            4 = Triplet method. If a triplet can be found in 3 cells then the triplets values can be removed from other cells in the area
            5 = Quartet method
            6 = Pointing pair
        '''
        if len(self.emptyCells) > 0:
            foundSomething = False
            self.updatePossibilities()
            if method == 0:
                print "[M0] Trying to find if some cells have only one possibility..."
                foundSomething = self.methodNakedSingle()
                if foundSomething == True:
                    print "...All unique possibilities found, let's go ahead..."
                else:
                    print "...Nothing found, let's work harder..."
                self.solve(method=1)
                
            if method == 1:
                print "[M1] Trying to find some values using Unique Number in Area Method..."
                foundSomething = self.methodUniqueCandidate()
                if foundSomething == True:
                    print "...Some values were found, let's go back to easier method..."
                    self.solve()
                else:
                    print "...No new value found, let's work harder..."
                    self.solve(method=2)
                    
            if method == 2:
                print "[M2] Trying to find if some value can only be found on one row/column per subgrid..."
                foundSomething = self.methodBlockInteraction()
                if foundSomething == True:
                    print "...Some values were found, let's go back to easier method..."
                    self.solve()
                else:
                    print "...No new value found, let's work harder..."
                    self.solve(method=3)
            
            if method == 3:
                """Naked pair method"""
                foundSomething = self.methodNakedPair()                  
                if foundSomething == True:
                    print "...Some possibilities have been removed, let's go back to easier methods..."
                    self.solve()
                else:
                    print "...No possibility removed, let's work harder!"
                    self.solve(method=4)
                    
            if method == 4:
                """Triplet method"""
                foundSomething = self.methodTriplet()
                if foundSomething == True:
                    print "...Some possibilities have been removed, let's go back to easier methods..."
                    self.solve()
                else:
                    print "...No possibility removed, let's work harder!"
                    self.solve(method=5)
            
            if method == 5:
                """Quartet method"""
                foundSomething = self.methodQuartet()
                if foundSomething == True:
                    print "...Some possibilities have been removed, let's go back to easier methods..."
                    self.solve()
                else:
                    print "...No possibility removed, let's work harder!"
                    self.solve(method=6)
                    
            if method == 6:
                """ Pointing pair method """
                foundSomething = self.methodPointingPair()
                if foundSomething == True:
                    print "...Some possibilities have been removed, let's go back to easier methods..."
                    self.solve()
                else:
                    print "...No possibility removed, let's work harder!"

        else:
            print "!!! Grid should be solved !!!"
            self.display()
            
    def getPairsInArea(self,area):
        ''' Returns a dictionary of all pairs and matching cells for the given area '''
        pairs = {}
        for cell in area.getCellsList():
            possibilities = []
            if len(cell.possibilities) == 2:
                possibilities.extend(cell.possibilities)
                possibilities.sort()
                if (possibilities[0],possibilities[1]) not in pairs.keys():
                    pairs[(possibilities[0],possibilities[1])] = []
                pairs[(possibilities[0],possibilities[1])].append(cell)
        return pairs
            
    def getPossibilityLocationInRow(self,value,row):
        ''' Returns all cells where the given value could be placed in the given row '''
        cells = [cell for cell in row.getEmptyCellsList() if value in cell.possibilities]
        return (len(cells),cells)
    
    def getPossibilityLocationInColumn(self,value,column):
        ''' Returns all cells where the given value could be placed in the given column '''
        cells = [cell for cell in column.getEmptyCellsList() if value in cell.possibilities]
        return (len(cells),cells)
    
    def getPossibilityLocationInSubgrid(self,value,subgrid):
        ''' Returns all cells where the given value could be placed in the given subgrid '''
        cells = [cell for cell in subgrid.getEmptyCellsList() if value in cell.possibilities]
        return (len(cells),cells)
    
    def getCellAreas(self,cell):
        '''Returns the [row, column, subgrid] the cell belongs to'''
        column = self.gridColumns[cell.x]
        row = self.gridRows[cell.y]
        gridId = cell.getSubgridId()
        grid = self.gridSubgrids[gridId]
        return [row,column,grid]
            
    def updateCellAreasMissingValues(self,cell):
        ''' Updates all SudokuAreas.missingValues for the areas the cell belongs to '''
        areas = self.getCellAreas(cell)
        for area in areas:
            area.updateMissingValues()
    
    def updatePossibilities(self,location="",i=None):
        ''' Updates SudokuCell.possibilities for a row, a column, a subgrid attached to a cell (one or all) or the entire grid at once'''
        if location == "":
            ''' Full Grid Update '''
            for cell in self.getCellsList():
                if cell.value == 0:
                    self.setCellPossibilities((cell.x,cell.y))
        if location == "row":
            ''' Specific row update '''
            row = self.gridRows[i]
            for cell in row.getCellsList():
                if cell.value == 0:
                    self.setCellPossibilities((cell.x,cell.y))
        if location == "column":
            ''' Specific column update '''
            col = self.gridColumns[i]
            for cell in col.getCellsList():
                if cell.value == 0:
                    self.setCellPossibilities((cell.x,cell.y))
        if location == "subgrid":
            ''' Specific subgrid update '''
            sub = self.gridSubgrids[i]
            for cell in sub.getCellsList():
                if cell.value == 0:
                    self.setCellPossibilities((cell.x,cell.y))
        if location == "cell":
            ''' Update of row,column and subgrid containing the cell '''
            (cx,cy) = i
            aid = self.allCells[i].getSubgridId()
            self.updatePossibilities("row", cy)
            self.updatePossibilities("column", cx)
            self.updatePossibilities("subgrid", aid)